package 代码随想录_动态规划.完全背包;

/**
 * @author zx
 * @create 2022-05-31 12:44
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[i]: 凑成目标正整数为i的排列个数为dp[i]
 * 2.确定递推公式
 *  求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
 * 3.dp数组如何初始化
 *  因为递推公式dp[i] += dp[i - nums[j]]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
 * 4.确定遍历顺序
 *  如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 *  如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 * 5.举例推导dp数组
 *
 */
public class 组合总和Ⅳ_377 {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 0;i <= target;i++){//背包
            for(int j = 0;j < nums.length;j++){//物品
                if(i - nums[j] >= 0){//背包要能容的下物品
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}
